package week_2;

public class text2 {
    public static void main(String[] args) {
        int[] stones=new int[]{31,26,33,21,40};
        System.out.println(lastStoneWeightII(stones));
    }
    public static int lastStoneWeightII(int[] stones) {
        //获得可选方案
        //int i=stones.length;
        //获得背包空间
        int sum=0;
        for (int index:stones){
            sum+=index;
        }
        //设计方案网格
        /**背包一共要考虑stones.length种方案的组合,背包的最大格子数为sum/2*/
        /*这里有个小坑,新建二维数组时,[]填写的是元素(注意!不是下标)个数*/
        int[][] bg=new int[stones.length+1][sum/2+1];
        for(int i=1;i<=stones.length;i++){//不断的添加可选方案数量
            for (int j=0;j<=sum/2;j++){//考虑背包  从小到大  的情况下能在 前i种方案  下得到的最大价值
                //如果装的下该方案,比较以下两者
                if (stones[i-1]<=j){
                    //1.之前在此背包大小下的最大价值 (它的上一个价值)
                    /*bg[i-1][j]*/
                    //2.当前方案价值(这一个价值) + (此时背包大小-装该方案所需背包大小)的最大价值(它的上一个价值)
                    /*stones[i-1]+bg[i-1][j-stones[i-1]]*/
                //取最大的一者作为此时背包大小与方案类型下的最大价值
                    bg[i][j] = bg[i-1][j]>=stones[i-1]+bg[i-1][j-stones[i-1]] ? bg[i-1][j] : stones[i-1]+bg[i-1][j-stones[i-1]] ;
                }else {//装不下的话,此时方案空间最大值就位之前方案 的同空间最大值
                    //来作为当前(i)个方案下(j)空间的最大价值
                    bg[i][j] = bg[i-1][j];
                }
            }
        }
        //bg[i(max)][j(max)]为最佳价值方案
        /*而读某个二维数组中元素数据时[]填写的是下标*/
        return sum-bg[stones.length][sum/2]*2;
    }
}
